package com.sf.algo.shortpath;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
/**
 * 路径代价的估算：F = G+H
 * G表示的是从起点到当前结点的实际路径代价
 * H表示当前结点到达最终结点的估计代价
 * F表示当前结点所在路径从起点到最终点预估的总路径代价
 * @author Administrator
 *
 */
public class ShortPathAlgo {
	private final static int BAR = 1;
	private final static int PATH = 0;
	private final static int DIRECT_VALUE = 1;
	private Queue<Node> openList = new PriorityQueue<>();
	private List<Node> closeList = new ArrayList<>();
	//private final static Logger logger = LoggerFactory.getLogger(ShortPathAlgo.class);
	private ShortPathAlgo() {
		
	}
	private static class Singleton {
		private static ShortPathAlgo instance;
		static {
			instance = new ShortPathAlgo();
		}
		private static ShortPathAlgo getInstance() {
			return instance;
		}
	}
	public static ShortPathAlgo getInstance() {
		return ShortPathAlgo.Singleton.getInstance();
	}
	public StartEndResult start(MapInfo mapInfo) {
		if(mapInfo == null) return null;
		openList.clear();
		closeList.clear();
		openList.add(mapInfo.getStart());
		return moveCurrentNode(mapInfo);
	}
	
	/**
	 * 判断传入的节点是否是终点
	 * @param endNode
	 * @param coord
	 * @return
	 */
	private boolean isEndNode(Coord endNode,Coord coord) {
		return coord != null && endNode.equals(coord);
	}
	/**
	 * 判断坐标是否在close中
	 * @param x
	 * @param y
	 * @return
	 */
	private boolean isCoordInClose(int x,int y) {
		if(closeList.isEmpty()) return false;
		for(Node node : closeList) {
			if(node.getCoord().getX() == x && node.getCoord().getY() == y) {
				return true;
			}
		}
		return false;
	}
	
	private boolean isCoordInClose(Coord coord) {
		return coord != null && isCoordInClose(coord.getX(),coord.getY());
	}
	/**
	 * 判断坐标能否加入到open列表中
	 * @param mapInfo
	 * @param x
	 * @param y
	 * @return
	 */
	private boolean canAddNodeToOpen(MapInfo mapInfo,int x,int y) {
		if (x<0 || x >= mapInfo.getWidth() || y < 0 || y >= mapInfo.getHight()) return false;
		if (mapInfo.getMaps()[x][y] == BAR) return false;
		if (isCoordInClose(x,y)) return false;
		return true;
	}
	/**
	 * 计算H的估值："曼哈顿法"，坐标分别取差值相加
	 * @param end
	 * @param coord
	 * @return
	 */
	private int calCH(Coord end,Coord coord) {
		return Math.abs(end.getX() - coord.getX()) + Math.abs(end.getY() - coord.getY());
	}
	/**
	 * 给定节点查看是否在open列表中
	 * @param coord
	 * @return
	 */
	private Node findNodeInOpen(Coord coord) {
		if (coord == null || openList.isEmpty()) return null;
		for(Node node : openList) {
			if (node.getCoord().equals(coord)) {
				return node;
			}
		}
		return null;
	}
	/**
	 * 添加邻居节点到OPEN列表中
	 * @param mapinfo
	 * @param current
	 * @param x
	 * @param y
	 * @param value
	 */
	private void addNeighborNodeToOpen(MapInfo mapInfo,Node current,int x,int y,int value) {
		if(canAddNodeToOpen(mapInfo, x, y)) {
			Node end = mapInfo.getEnd();
			Coord coord = new Coord(x,y);
			int g = current.getG() + value;
			Node child = findNodeInOpen(coord);
			if (child == null) {
				int h = calCH(end.getCoord(),coord);
				if(isEndNode(end.getCoord(),coord)) {//如果给定的节点，即邻居节点是终点，则当前节点的孩子节点就是终点
					child = end;
					child.setParent(current);
					child.setG(g);
					child.setH(h);
				} else {
					child = new Node(coord,current,g,h);//如果给定的邻居节点不是终点，则当前节点为邻居节点的父节点
				}
				openList.add(child);//邻居节点加入到open列表中
			} else if(child.getG() > g){//如果最新的g值小于当前的值,则需更新这个G值
				child.setG(g);
				child.setParent(current);//邻居节点的父节点就是当前节点
				openList.add(child);
			}
		}
	}
	
	private void addAllNeighborNodeToOpen(MapInfo mapInfo,Node current) {
		int x = current.getCoord().getX();
		int y = current.getCoord().getY();
		addNeighborNodeToOpen(mapInfo,current, x, y + 1, DIRECT_VALUE); //向左
		addNeighborNodeToOpen(mapInfo,current, x, y - 1, DIRECT_VALUE); //向右
		addNeighborNodeToOpen(mapInfo,current, x-1, y, DIRECT_VALUE); //向上
		addNeighborNodeToOpen(mapInfo,current, x+1, y, DIRECT_VALUE); //向下
	}
	
	private StartEndResult drawPath(int [][] maps,Node end) {
		if (end == null || maps == null) return null;
		List<Coord> stack = new ArrayList<>();
		int allScore = end.getG();
		//System.out.println("总代价:"+end.getG());
		//logger.info("总代价:{}",end.getG());
		while (end != null) {
			Coord c = end.getCoord();
			//System.out.println("x = " + c.getX() + " y = " + c.getY());
			stack.add(c);
			maps[c.getX()][c.getY()] = PATH;
			end = end.getParent();
		}
		Collections.reverse(stack);
		return new StartEndResult(allScore,stack);
	}
	/**
	 * 移动当前节点
	 * @param mapInfo
	 */
	private StartEndResult moveCurrentNode(MapInfo mapInfo) {
		while ( !openList.isEmpty() ) {
			if (isCoordInClose(mapInfo.getEnd().getCoord())) {
				return drawPath(mapInfo.getMaps(),mapInfo.getEnd());
			}
			Node current = openList.poll();
			
			closeList.add(current);
			addAllNeighborNodeToOpen(mapInfo,current);
		}
		return null;
	}
	 
}
